package leetcode;

/*
491. 递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
*/

import java.util.ArrayList;
import java.util.List;

public class problems_491 {
    public static void main(String[] args) {
        System.out.println(new Solution().findSubsequences(new int[]{10, 20, 30}));
    }

    static class Solution {
        private List<List<Integer>> res = new ArrayList<List<Integer>>();
        private List<Integer> temp = new ArrayList<>();

        public List<List<Integer>> findSubsequences(int[] nums) {
            if (nums == null) {
                return null;
            }
            dfs(0, Integer.MIN_VALUE, nums);
            return res;
        }

        private void dfs(int curIndex, int preValue, int[] nums) {
            if (curIndex >= nums.length) {  // 遍历结束
                if (temp.size() >= 2) {
                    res.add(new ArrayList<>(temp));
                }
                return;
            }

            if (nums[curIndex] >= preValue) {   // 将当前元素加入，并向后遍历
                temp.add(nums[curIndex]);
                dfs(curIndex + 1, nums[curIndex], nums);
                temp.remove(temp.size() - 1);
            }
            if (nums[curIndex] != preValue) {   // 不遍历 重复元素
                dfs(curIndex + 1, preValue, nums);  // 将下一个元素加入，并向后遍历
            }
        }
    }


//    static class Solution {
//        List<List<Integer>> ret = new ArrayList<>();
//        // 重复判断用
//        List<String> duplicateList = new ArrayList<>();
//
//        public List<List<Integer>> findSubsequences(int[] nums) {
//            // 起始点遍历
//            for (int i = 0; i < nums.length - 1; i++) {
//                Stack<Integer> stack = new Stack();
//                stack.push(nums[i]);
//                dfs(nums, stack, i + 1);
//            }
//            return ret;
//        }
//
//        //
//        private void dfs(int[] nums, Stack<Integer> stack, int index) {
//            for (int i = index; i < nums.length; i++) {
//                // 跳出
//                if (stack.peek() > nums[i]) continue;
//                // 追加
//                stack.push(nums[i]);
////                System.out.println("fn,index:" + index + ",i:" + i + ",stack:" + stack);
//                List<Integer> list = (List<Integer>) stack.clone();
//                String str = listToString(list);
//                if (!duplicateList.contains(str)) {
//                    ret.add(list);
//                    duplicateList.add(str);
//                }
//                dfs(nums, stack, i + 1);
//                stack.pop();
//            }
//        }
//
//        //
//        private String listToString(List<Integer> list) {
//            StringBuffer ret = new StringBuffer(list.size() * 2);
//            for (int i = 0; i < list.size(); i++) {
//                ret.append(list.get(i));
//            }
//            return ret.toString();
//        }
//    }
}